<TITLE>prob018: water bucket problem</TITLE>
<HR><!------------------------------------------------------------------------>
<CENTER>
<H1>prob018: water bucket problem</H1>

<TABLE>
<TR> <TD> proposed by
     <TD ALIGN=LEFT> <A HREF="http://www.cs.york.ac.uk/~tw">
          <B>Toby Walsh</B></A> 
          <ADDRESS><a href="mailto:tw@cs.york.ac.uk">
          tw@cs.york.ac.uk</a></ADDRESS>
</TABLE>
</CENTER>
<HR><!------------------------------------------------------------------------>
<H3> Results </H3>
Robert Matthews <A HREF="http://www.telegraph.co.uk:80/et?ac=000112753058119&rtmo=LihilyKd&atmo=99999999&pg=/et/99/9/2/ecfmaze02.html">suggests</A> 
that the problem can be turned into a maze
if one denotes "position" in the
maze by the contents of the three buckets in fixed order, with the
problem being to get from "8-0-0" - that is, 8 pints in the biggest
bucket, with the others empty, to "4-4-0" - four pints in the 8 and
5-pint buckets, the other one empty. He reports that 
Ian Stewart at Warwick has
shown that "depth-first search" can solve this maze problem. 

<P>
In a later article, he reports that several people have sent
him solutions involving seven transfers of water (some using 
ingenious graphical solution methods). He asks if this is
optimal since it seems rather high. 

<P>
A simple <A HREF="enumerate.pl">Prolog program</A> for enumerating
solutions shows that 7 pourings is 
indeed optimal and the solution is unique. 

<P>
<TT>
8-0-0,3-5-0,3-2-3,6-2-0,6-0-2,1-5-2,1-4-3,4-4-0
</TT>


<HR><!------------------------------------------------------------------------>

<UL>

 <A HREF="../../index.html"> Back</A> to CSPLib home page.


